package com.example.lcode.backtrack;

public class Question79 {

    public boolean exist(char[][] board, String word) {
        // 方向 y,x
        int [][]dirct = new int[][]{{1,0},{0, 1}, {-1, 0}, {0, -1}};
        int wordLength = word.length();
        StringBuilder str = new StringBuilder("");
        for (int i = 0; i < board[0].length; i++) {
            for (int j = 0; j < board.length; j++) {
                if (!String.valueOf(board[j][i]).equals(word.substring(0, 1))) {
                    continue;
                }
                if (doExist(board, word, dirct, wordLength, str.append(word.substring(0, 1)), i, j)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean doExist(char[][] board, String word, int[][] dirct, int wordLength, StringBuilder str, int xIndex, int yIndex) {
        if (wordLength == str.length()) {
            return true;
        }
        boolean sign = false;
        for (int i = 0; i < dirct.length; i++) {
            if (i == 1 && xIndex == board[0].length - 1 || i == 0 && yIndex == board.length - 1 || i == 3 && xIndex < 0 || i == 2 && yIndex < 0) {
                continue;
            }
            int nextXIndex = xIndex + dirct[i][1];
            int nextYIndex = yIndex + dirct[i][0];
            String temp = String.valueOf(board[nextYIndex][nextXIndex]);
            if (!temp.equals(word.substring(str.length(), str.length() + 1))){
                continue;
            } else if (temp.equals(word.substring(str.length(), str.length() + 1))) {
                str.append(temp);
                if (doExist(board, word, dirct, wordLength, str, nextXIndex, nextYIndex)) {
                    sign = true;
                    break;
                }
                str.deleteCharAt(temp.length() - 1);
            } else if (str.length() == 0) {
                if (doExist(board, word, dirct, wordLength, str, nextXIndex, nextYIndex)) {
                    sign = true;
                    break;
                }
            }
        }
        return sign;
    }

    public static void main(String[] args) {
        Question79 question79 = new Question79();
        char[][] board = new char[][]{{'A', 'B', 'C', 'E'},{'S','F','C','S'},{'A','D', 'E', 'E'}};
        String word = "ABCCED";
        boolean exist = question79.exist(board, word);
        System.out.println(exist);
    }

}
